import java.util.*;

public class ThroneInheritance {
    String KingName;

    Map<String,RoyalMember> royalMemberMap;

    class RoyalMember{
        String name;
        List<RoyalMember> children;
        boolean isDead=false;

        RoyalMember(String name){
            this.name=name;
            this.children=new ArrayList<>();
        }

        void addChild(String childName){
            RoyalMember child=new RoyalMember(childName);
            this.children.add(child);
            royalMemberMap.put(childName,child);
        }
    }

    public ThroneInheritance(String kingName) {
        this.KingName=kingName;
        this.royalMemberMap=new HashMap<>();
        this.royalMemberMap.put(kingName,new RoyalMember(kingName));
    }

    public void birth(String parentName, String childName) {
        RoyalMember parent=this.royalMemberMap.get(parentName);
        parent.addChild(childName);
    }

    public void death(String name) {
        this.royalMemberMap.get(name).isDead=true;
    }

    public void travel(RoyalMember tmpMember,List<String> order){
        if(!tmpMember.isDead){
            order.add(tmpMember.name);
        }
        for (RoyalMember member:tmpMember.children) {
            travel(member,order);
        }
    }

    public List<String> getInheritanceOrder() {
        RoyalMember King=this.royalMemberMap.get(this.KingName);
        List<String> order=new LinkedList<>();
        travel(King,order);
        return order;
    }
}
